/**	
 *  Copyright (c) 2005-2014 VedantaTree all rights reserved.
 * 
 *  This file is part of ExpressionOasis.
 *
 *  ExpressionOasis is free software. You can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  ExpressionOasis is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL 
 *  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES 
 *  OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
 *  ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE 
 *  OR OTHER DEALINGS IN THE SOFTWARE.See the GNU Lesser General Public License 
 *  for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with ExpressionOasis. If not, see <http://www.gnu.org/licenses/>.
 *  
 *  Please consider to contribute any enhancements to upstream codebase. 
 *  It will help the community in getting improved code and features, and 
 *  may help you to get the later releases with your changes.
 */
package org.vedantatree.expressionoasis.grammar;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.vedantatree.expressionoasis.config.ConfigFactory;
import org.vedantatree.expressionoasis.grammar.rules.IProductionRule;
import org.vedantatree.expressionoasis.grammar.rules.ProductionRule;
import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;


/**
 * This is the default XML based grammar implementation. It read the production
 * rules from a XML file, and populate its rule sets. Use of XML makes it highly
 * customizable without making any change to code.
 * 
 * TODO
 * Can we remove operators array and use precedence map keys?
 * DefaultXMLGrammar can be loosely coupled with Compiler, i.e. can be picked from
 * configuration.
 * 
 * @author Parmod Kamboj
 * @author Mohit Gupta
 * @version 1.0
 * 
 *          Modified to use sets and contains() rather than arrays and array searching.
 *          Removed redundant check for isFunction in isOperator, as this is checked in isUnary.
 * 
 *          More to do here. Should move grammar into main config file and read via Simple XML framework.
 * 
 * @author Kris Marwood
 * @version 1.1
 * 
 *          Made grammar file path configurable by reading it from configuration
 * 
 * @author Mohit Gupta
 * @version 1.2
 * @since 3.1
 */
public class DefaultXMLGrammar implements Grammar
{

	private static Log				LOGGER					= LogFactory.getLog( DefaultXMLGrammar.class );

	/**
	 * File path for grammar configuration.
	 */
	public final String				FILE_PATH;

	/**
	 * This is the constant name for production rules tag in XML
	 */
	public static final String		PRODUCTION_RULES		= "productionRules";

	/**
	 * This is the constant name for binary operators tag in XML
	 */
	private static final String		BINARY_OPERATORS		= "binaryOperators";

	/**
	 * This is the constant name for unary operators tag in XML
	 */
	public static final String		UNARY_OPERATORS			= "unaryOperators";

	/**
	 * This is the constant name for functions tag in XML
	 */
	public static final String		FUNCTIONS				= "functions";

	/**
	 * This is the constant name for delimiters tag in XML
	 */
	public static final String		DELIMITERS				= "delimiters";

	/**
	 * This is the constant name for brackets tag in XML
	 */
	public static final String		BRACKETS				= "brackets";

	/**
	 * This is the constant name for ignore blank tag in XML
	 */
	public static final String		IGNORE_BLANK			= "ignoreBlank";

	/**
	 * This is the constant name for true tag in XML
	 */
	public static final String		TRUE					= "true";

	/**
	 * This is the constant name for name tag in XML
	 */
	public static final String		NAME					= "name";

	/**
	 * This is the constant name for bracket tag in XML
	 */
	public static final String		BRACKET					= "bracket";

	/**
	 * This is the constant name for left tag in XML
	 */
	public static final String		LEFT					= "left";

	/**
	 * This is the constant name for right tag in XML
	 */
	public static final String		RIGHT					= "right";

	/**
	 * This is the constant name for operator tag in XML
	 */
	public static final String		OPERATOR				= "operator";

	/**
	 * This is the constant name for precedence tag in XML
	 */
	public static final String		PRECEDENCE				= "precedence";

	/**
	 * This is the constant name for delimiter tag in XML
	 */
	public static final String		DELIMITER				= "delimiter";

	/**
	 * This is the constant name for production rule tag in XML
	 */
	public static final String		PRODUCTION_RULE			= "productionRule";

	/**
	 * This is the constant name for approachable pattern tag in XML
	 */
	public static final String		APPROACHABLE_PATTERN	= "approchablePattern";

	/**
	 * This is the constant name for allowed pattern tag in XML
	 */
	public static final String		ALLOWED_PATTERN			= "allowedPattern";

	/**
	 * Set of production rules of this grammar.
	 */
	private Set<IProductionRule>	productionRules;

	/**
	 * Set of unary operators.
	 */
	private Set<String>				unaryOperators;

	/**
	 * Set of binary operators.
	 */
	private Set<String>				binaryOperators;

	/**
	 * Set of of functions.
	 */
	private Set<String>				functions;

	/**
	 * Set of of delimiters.
	 */
	private Set<String>				delimiters;

	/**
	 * Array container of bracket pair
	 */
	private String[][]				brackets;

	/**
	 * Map container for precedence of binary operators, binary operator as key and
	 * precedence as value.
	 */
	private Map<String, Integer>	binaryPrecedences;

	/**
	 * Map container for precedence of unary operators, unary operator as key and
	 * precedence as value.
	 */
	private Map<String, Integer>	unaryPrecedences;

	/**
	 * This is the indicator whether to ignore the blank or not during parsing.
	 */
	private boolean					ignoreBlank;

	/**
	 * Constructs the grammar
	 */
	public DefaultXMLGrammar()
	{
		String grammarPath = ConfigFactory.getConfig().getGrammarPath();
		FILE_PATH = ( grammarPath != null && grammarPath.trim().length() > 0 ) ? grammarPath : "grammar.xml";

		configure();
	}

	/**
	 * Checks whether the token is a delimiter or not.
	 * 
	 * @param token the token
	 * @return <code>true</code> if the token is delimiter <code>false</code> otherwise.
	 */
	public boolean isDelimiter( ExpressionToken token )
	{
		return isDelimiter( token.getValue() );
	}

	/**
	 * Checks whether the token is a delimiter or not.
	 * 
	 * @param token the token
	 * @return <code>true</code> if the token is delimiter <code>false</code> otherwise.
	 */
	public boolean isDelimiter( String token )
	{
		return delimiters.contains( token );
	}

	/**
	 * Checks whether the given token is approachable using any of the pattern
	 * or not.
	 * 
	 * Given token can be partially or fully constructed token during
	 * parsing process. Parser generally calls this method to check whether the
	 * current token can be combined with next character of expression to form
	 * some meaningful token or not. If not, then it utilize the existing
	 * collected characters as one token, otherwise it keep collecting
	 * characters.
	 * 
	 * @param token the token, partially or full constructed, to check whether
	 *        it can approach to any expression token pattern or not.
	 * @return <code>true</code> if the token pattern is approachable <code>false</code> otherwise.
	 */
	public boolean isApproachable( String token )
	{
		boolean result = false;
		for( IProductionRule productionRule : productionRules )
		{
			if( productionRule.isApproaching( token ) )
			{
				result = true;
				break;
			}
		}
		return result;
	}

	/**
	 * Checks whether the token is allowed or not.
	 * 
	 * A token is fully constructed token. Parser generally calls this method to
	 * check whether the current token is a valid token as per the production
	 * rules or not.
	 * 
	 * @param token the token which is to be checked for its validity
	 * @return <code>true</code> if the token is allowed <code>false</code> otherwise.
	 */
	public boolean isAllowed( String token )
	{
		boolean result = false;
		for( IProductionRule productionRule : productionRules )
		{
			if( productionRule.isAllowed( token ) )
			{
				result = true;
				break;
			}
		}
		return result;
	}

	/**
	 * Checks whether to ignore the blanks in expression or not. It tells the
	 * parser whether to exclude the extra blanks while parsing or not.
	 * 
	 * @return <code>true</code> if parser wants to exclude the blanks <code>false</code> otherwise.
	 */
	public boolean isIgnoreBlank()
	{
		return ignoreBlank;
	}

	/**
	 * Checks whether the given token is an operator or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token is an operator <code>false</code> otherwise
	 */
	public boolean isOperator( ExpressionToken token )
	{
		return isOperator( token.getValue() );
	}

	/**
	 * Checks whether the given token is an operator or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token is an operator <code>false</code> otherwise
	 */
	public boolean isOperator( String token )
	{
		return isBinaryOperator( token ) || isUnary( token );
	}

	/**
	 * Checks whether the given token is a binary operator or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token is a binary operator <code>false</code> otherwise
	 */
	public boolean isBinaryOperator( ExpressionToken token )
	{
		return isBinaryOperator( token.getValue() );
	}

	/**
	 * Checks whether the given token is a binary operator or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token is a binary operator <code>false</code> otherwise
	 */
	public boolean isBinaryOperator( String token )
	{
		return binaryOperators.contains( token );
	}

	/**
	 * Adds a function name to the grammar.
	 * 
	 * TODO: should probably look up function precedence from grammar config file
	 * rather than hard coding it to 13.
	 * 
	 * @param name name of the function to add
	 */
	public void addFunction( String functionName )
	{
		functions.add( functionName );
		unaryPrecedences.put( functionName, 13 );

	}

	/**
	 * Checks whether the token is an function or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token is an function <code>false</code> otherwise
	 */
	public boolean isFunction( ExpressionToken token )
	{
		return isFunction( token.getValue() );
	}

	/**
	 * Checks whether the token is an function or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token is an function <code>false</code> otherwise
	 */
	public boolean isFunction( String token )
	{
		return functions.contains( token );
	}

	/**
	 * Checks whether the given operator is a unary operator or not.
	 * 
	 * @param operator the operator to check
	 * @return <code>true</code> if the operator is used as unary operator <code>false</code> otherwise.
	 */
	public boolean isUnary( ExpressionToken operator )
	{
		return isUnary( operator.getValue() );
	}

	/**
	 * Checks whether the given operator is a unary operator or not.
	 * 
	 * @param operator the operator to check
	 * @return <code>true</code> if the operator is used as unary operator <code>false</code> otherwise.
	 */
	public boolean isUnary( String operator )
	{
		return unaryOperators.contains( operator ) || isFunction( operator );
	}

	/**
	 * Checks whether the token is a left bracket or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token can be used as left bracket <code>false</code> otherwise.
	 */
	public boolean isLeftBracket( ExpressionToken token )
	{
		return isLeftBracket( token.getValue() );
	}

	/**
	 * Checks whether the token is a left bracket or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token can be used as left bracket <code>false</code> otherwise.
	 */
	public boolean isLeftBracket( String token )
	{
		boolean result = false;
		int length = brackets == null ? 0 : brackets.length;

		for( int i = 0; i < length; i++ )
		{
			result = token.equals( brackets[i][0] );

			if( result )
			{
				break;
			}
		}

		return result;
	}

	/**
	 * Checks whether the token is a right bracket or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token can be used as right bracket <code>false</code> otherwise.
	 */
	public boolean isRightBracket( ExpressionToken token )
	{
		return isRightBracket( token.getValue() );
	}

	/**
	 * Checks whether the token is a right bracket or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token can be used as right bracket <code>false</code> otherwise.
	 */
	public boolean isRightBracket( String token )
	{
		boolean result = false;
		int length = brackets == null ? 0 : brackets.length;

		for( int i = 0; i < length; i++ )
		{
			result = token.equals( brackets[i][1] );

			if( result )
			{
				break;
			}
		}

		return result;
	}

	/**
	 * Check whether the given token is a bracket or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token is a bracket <code>false</code> otherwise
	 */
	public boolean isBracket( ExpressionToken token )
	{
		return isBracket( token.getValue() );
	}

	/**
	 * Check whether the given token is a bracket or not.
	 * 
	 * @param token the token to check
	 * @return <code>true</code> if the token is a bracket <code>false</code> otherwise
	 */
	public boolean isBracket( String token )
	{
		return isRightBracket( token ) || isLeftBracket( token );
	}

	/**
	 * Returns the opposite bracket for the given bracket.
	 * 
	 * @param bracket the bracket for which we need to find the opposite bracket
	 * @return the opposite part of bracket w.r.t given bracket
	 */
	public String getOppositeBracket( String bracket )
	{
		String result = null;
		int length = brackets == null ? 0 : brackets.length;

		for( int i = 0; i < length; i++ )
		{
			int index = search( brackets[i], bracket );

			if( index != -1 )
			{
				result = index == 1 ? brackets[i][0] : brackets[i][1];

				break;
			}
		}

		return result;
	}

	/**
	 * Gets the precedence order of the given operator
	 * 
	 * @param operator the operator to check for precedence
	 * @param isUnary true if the operator is unary, as an operator can behave
	 *        either as unary or as binary
	 * @return the precedence order of the operator
	 */
	public int getPrecedenceOrder( ExpressionToken operator, boolean isUnary )
	{
		return getPrecedenceOrder( operator.getValue(), isUnary );
	}

	/**
	 * Gets the precedence order of the given operator
	 * 
	 * @param operator the operator to check for precedence
	 * @param isUnary true if the operator is unary, as an operator can behave
	 *        either as unary or as binary
	 * @return the precedence order of the operator
	 */
	public int getPrecedenceOrder( String operator, boolean isUnary )
	{
		return isUnary ? ( (Integer) unaryPrecedences.get( operator ) ).intValue() : ( (Integer) binaryPrecedences
				.get( operator ) ).intValue();
	}

	/**
	 * Configures the grammar object with specified XML file
	 */
	private void configure()
	{

		// ExpressionOasisConfig config = ConfigFactory.getConfig();
		// GrammarConfig grammarConfig = config.getGrammarConfig();
		// System.err.println("delmiters: " + grammarConfig.getDelimiters());

		try
		{
			DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
			factory.setValidating( true );

			DocumentBuilder builder = factory.newDocumentBuilder();

			LOGGER.debug( "resourcePath[" + getClass().getClassLoader().getResource( "" ) );
			Document document = builder.parse( getClass().getClassLoader().getResourceAsStream( FILE_PATH ) );
			Element root = document.getDocumentElement();

			// Extracting production rules
			NodeList nodeList = root.getChildNodes();
			int length = nodeList.getLength();

			for( int i = 0; i < length; i++ )
			{
				Node childNode = nodeList.item( i );
				String nodeName = childNode.getNodeName();

				if( childNode.getNodeType() == Node.ELEMENT_NODE )
				{
					if( PRODUCTION_RULES.equals( nodeName ) )
					{
						buildProductionRules( (Element) childNode );
					}
					else if( BINARY_OPERATORS.equals( nodeName ) )
					{
						buildBinaryOperators( (Element) childNode );
						loadBinaryPrecedence( (Element) childNode );
					}
					else if( UNARY_OPERATORS.equals( nodeName ) )
					{
						buildUnaryOperators( (Element) childNode );
						loadUnaryPrecedence( (Element) childNode );
					}
					else if( FUNCTIONS.equals( nodeName ) )
					{
						buildFunctions( (Element) childNode );
						loadFunctionPrecedence( (Element) childNode );
					}
					else if( DELIMITERS.equals( nodeName ) )
					{
						buildDelimiters( (Element) childNode );
					}
					else if( BRACKETS.equals( nodeName ) )
					{
						loadBrackets( (Element) childNode );
					}
					else if( IGNORE_BLANK.equals( nodeName ) )
					{
						ignoreBlank = TRUE.equals( ( (Element) childNode ).getAttribute( NAME ) );
					}
				}
			}
		}
		catch( Exception ex )
		{
			throw new RuntimeException( "Error while loading the configurations.", ex );
		}
	}

	/**
	 * Loads the brackets from the XML configuration
	 * 
	 * @param childNode
	 */
	private void loadBrackets( Element childNode )
	{
		NodeList childList = childNode.getElementsByTagName( BRACKET );
		int childLength = childList.getLength();
		brackets = new String[childLength][2];

		for( int j = 0; j < childLength; j++ )
		{
			Element subChildNode = (Element) childList.item( j );
			brackets[j][0] = subChildNode.getAttribute( LEFT );
			brackets[j][1] = subChildNode.getAttribute( RIGHT );
		}
	}

	/**
	 * Loads the precedence of the binary operators
	 * 
	 * @param childNode
	 */
	private void loadBinaryPrecedence( Element childNode )
	{
		if( binaryPrecedences == null )
		{
			binaryPrecedences = new HashMap<String, Integer>();
		}

		loadPrecedence( childNode, binaryPrecedences );
	}

	/**
	 * Loads the precedence of the unary operators
	 * 
	 * @param childNode
	 */
	private void loadUnaryPrecedence( Element childNode )
	{
		if( unaryPrecedences == null )
		{
			unaryPrecedences = new HashMap<String, Integer>();
		}

		loadPrecedence( childNode, unaryPrecedences );
	}

	/**
	 * Loads the precedence of the functions
	 * 
	 * @param childNode
	 */
	private void loadFunctionPrecedence( Element childNode )
	{
		if( unaryPrecedences == null )
		{
			unaryPrecedences = new HashMap<String, Integer>();
		}

		loadPrecedence( childNode, unaryPrecedences );
	}

	/**
	 * Loads the precedence in the given map.
	 * 
	 * @param childNode
	 *        the operators node
	 * @param precedences
	 *        the map.
	 */
	private void loadPrecedence( Element childNode, Map<String, Integer> precedences )
	{
		NodeList childList = childNode.getElementsByTagName( OPERATOR );
		int childLength = childList.getLength();

		for( int j = 0; j < childLength; j++ )
		{
			Element subChildNode = (Element) childList.item( j );
			String operator = subChildNode.getAttribute( NAME );
			String precedence = subChildNode.getAttribute( PRECEDENCE );
			precedences.put( operator, new Integer( Integer.parseInt( precedence ) ) );
		}
	}

	/**
	 * Builds the delimiters
	 * 
	 * @param childNode
	 *        the node delimiters
	 */
	private void buildDelimiters( Element childNode )
	{
		delimiters = buildSetByAttribute( childNode, DELIMITER, NAME );
	}

	/**
	 * Builds the operators
	 * 
	 * @param childNode
	 *        the node for operators
	 */
	private void buildBinaryOperators( Element childNode )
	{
		binaryOperators = buildSetByAttribute( childNode, OPERATOR, NAME );
	}

	/**
	 * Builds the unary operators
	 * 
	 * @param childNode
	 *        the node for unary operators
	 */
	private void buildUnaryOperators( Element childNode )
	{
		unaryOperators = buildSetByAttribute( childNode, OPERATOR, NAME );
	}

	/**
	 * Builds the functions
	 * 
	 * @param childNode
	 *        the node for unary operators
	 */
	private void buildFunctions( Element childNode )
	{
		functions = buildSetByAttribute( childNode, OPERATOR, NAME );
	}

	/**
	 * Builds the production rules
	 * 
	 * @param childNode
	 *        the node for production rules
	 */
	private void buildProductionRules( Element childNode )
	{
		NodeList childList = childNode.getElementsByTagName( PRODUCTION_RULE );
		int childLength = childList.getLength();
		productionRules = new HashSet<IProductionRule>( childLength );

		for( int j = 0; j < childLength; j++ )
		{
			Element subChildNode = (Element) childList.item( j );
			ProductionRule rule = new ProductionRule( subChildNode.getAttribute( NAME ),
					subChildNode.getAttribute( APPROACHABLE_PATTERN ), subChildNode.getAttribute( ALLOWED_PATTERN ) );

			productionRules.add( rule );
		}
	}

	/**
	 * Builds the the set of string for attribute passed by the argument for
	 * the elements specified by the tag
	 * 
	 * @param childNode the node delimiters
	 * @param attribute the attribute for which to build the string set.
	 * @param tag the tag for which the elements are identified.
	 * @return the string set.
	 */
	private Set<String> buildSetByAttribute( Element childNode, String tag, String attribute )
	{
		NodeList childList = childNode.getElementsByTagName( tag );
		int childLength = childList.getLength();
		Set<String> set = new HashSet<String>( childLength );

		for( int j = 0; j < childLength; j++ )
		{
			Element subChildNode = (Element) childList.item( j );
			set.add( subChildNode.getAttribute( attribute ) );
		}

		return set;
	}

	/**
	 * Searches the element in the string array
	 * 
	 * @param array the string elements array
	 * @param element the element to search
	 * @return the index of element in array, <code>-1</code> if not found
	 */
	private int search( String[] array, String element )
	{
		int index = -1;
		int length = array == null ? 0 : array.length;

		for( int i = 0; i < length; i++ )
		{
			if( element == null )
			{
				if( array[i] == null )
				{
					index = i;

					break;
				}
			}
			else if( element.equals( array[i] ) )
			{
				index = i;

				break;
			}
		}

		return index;
	}

	/**
	 * Runs the test for grammar.
	 */
	public static void main( String[] args )
	{
		DefaultXMLGrammar grammar = new DefaultXMLGrammar();
		grammar.isOperator( "+" );
	}

}